//
// Created by admin on 2024-8-26
//
/*二分查找变形
 *查找第一个/ 最后一个值等于给定值的元素  锚定法
 * OJ: https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
 *查找第一个等于给定值的元素
  *查找最后一个小于等于 target 的元素，*
 * 讲解:
 * https://www.cnblogs.com/sunshuyi/p/12681088.html
 * */

#include <iostream>
#include <vector>

using namespace std;

// 查找第一个等于给定值的元素  用锚定的方法
int searchFirstEqual(vector<int> v, int x)
{
    int l = 0, r = v.size() - 1;
    int first_equal = -1;
    while (l <= r)
    {
        int m = (l + r) / 2;
        if (x < v[m])
            r = m - 1;
        else if (x > v[m])
            l = m + 1;
        else
        {
            first_equal = m;
            r = m - 1;
        }
    }
    return first_equal;
}

// 查找第一个大于等于给定值的元素
// (查找大于等于给定值 最左边的元素)
int searchFirstEqualLarge(vector<int> v, int x)
{
    int l = 0, r = v.size() - 1;
    int first_le = -1;
    while (l <= r)
    {
        int m = (r + l) / 2;
        if (v[m] >= x)
        {
            first_le = m;
            r = m - 1;
        } else
            l = m + 1;
    }
    return first_le;
}

// 查找最后一个等于target的元素
int searchLastEqual(vector<int> v, int x)
{
    int t = -1,l = 0,r =v.size();
    while(l<=r)
    {
       int m = r+(l-r) /2;
       if (x<v[m])
           r=m-1;
       else if(x>v[m])
           l=m+1;
       else
       {
           t=m;
           l=m+1;
       }
    }
    return t;
}

// 查找最后一个小于等于给定值的元素
// 给定值x大于元素的最右边一个
int searchLastLessEqual(vector<int> v, int x)
{
    int l = 0, r = v.size() - 1;
    int t = -1;
    while (l <= r)
    {
        int m = (l + r) / 2;
        if (x < v[m])
        {
            r = m - 1;
        } else
        {
            t = m;
            l = m + 1;
        }
    }
    return t;
}

int main()
{
    //                0   1  2  3  4  5  6  7  8  9  10 11 12
    vector<int> l = {-11, 0, 0, 1, 1, 1, 2, 2, 3, 5, 7, 9, 10};
//    vector<int> l ={1};
//    cout << searchFirstEqual(l,9) << endl;
//    cout<<searchFirstEqualLarge(l,1)<<endl;
    cout << searchLastEqual(l, 5) << endl;
//    cout << searchLastLessEqual(l, 1) << endl;
    return 0;
}